package LeetCode热题HOT100;

import java.util.ArrayList;
import java.util.List;

public class p22括号生成 {

    public List<String> generateParenthesis(int n) {
        //回溯+剪枝
        //剪枝：当左括号个数 > n || 右括号个数 > 左括号个数，直接返回
        List<String> res=new ArrayList<>();
        if(n==0) {
            return res;
        }

        StringBuilder sb=new StringBuilder();

        backTrack(res,"",n,0,0);
        return res;

    }

    private void backTrack(List<String> res, String path, int n, int leftCount, int rightCount) {
        //剪枝
        if (leftCount>n || rightCount>leftCount) {
            return;
        }
        //确定递归出口
        if (path.length()==n*2) {
            res.add(path);
            return;
        }

        //确定单词递归逻辑
        backTrack(res,path+"(",n,leftCount+1,rightCount);
        backTrack(res,path+")",n,leftCount,rightCount+1);
        //因为每一次尝试，都使用新的字符串变量，所以无需回溯
    }

    public static void main(String[] args) {

        System.out.println();
        new p22括号生成().generateParenthesis(2);
//        List<String> res=new ArrayList<>();
//        StringBuilder sb=new StringBuilder();
//        sb.append("aaaa");
//        res.add(sb.toString());
//        System.out.println(res);
//        sb.append("bbbb");
//        res.add(sb.toString());
//        System.out.println(res);
    }
}
